English+GermanWikipedia - /page/entry.mu

Micron Document

<!DOCTYPE html>

<title>Bottom-Up-Heapsort</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Bottom-Up-Heapsort</h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">BottomUp-Heapsort ist ein <a href="Sortierverfahren" title="Sortierverfahren">Sortieralgorithmus</a>, der u. a. <a href="1990" title="1990">1990</a> von <a href="Ingo_Wegener" title="Ingo Wegener">Ingo Wegener</a> vorgestellt wurde und im Durchschnitt besser als <a href="Quicksort" title="Quicksort">Quicksort</a> arbeitet,

falls man Vergleichsoperationen hinreichend stark gewichtet. Es ist eine Variante von <a href="Heapsort" title="Heapsort">Heapsort</a>, die vor allem zur Sortierung sehr großer Datenmengen geeignet ist, wenn (im Vergleich zu den notwendigen Vertauschungsoperationen) ein relativ hoher Aufwand pro Vergleichsoperation erforderlich ist.

Diese Variante wurde allerdings bereits <a href="1986" title="1986">1986</a> von Svante Carlsson analysiert,

der letztlich eine weitere Variante fand, die sogar eine <a href="Zeitkomplexit%C3%A4t" title="Zeitkomplexität">worst-case</a>-Laufzeit von nur n log n + O(n log log n) Vergleichen hat. Entdeckt wurde dieser Bottom-Up-Heapsort bereits von <a href="Robert_Floyd" title="Robert Floyd">Robert W Floyd</a> (bei einer Überarbeitung des ursprünglichen

Heapsorts von Williams), der aber das Laufzeitverhalten dieser Variante nicht beweisen konnte.

Er benötigt zum Sortieren einer Folge von n Schlüsseln

im schlechtesten Fall nur 1,5 n log n + 2n Schlüsselvergleiche.

Im Durchschnittsfall benötigt BottomUp-Heapsort nur n log n + O(n) Schlüsselvergleiche.

<div class="mw-heading mw-heading2"><h2 id="Prinzip_der_Sortierung">Prinzip der Sortierung</h2></div>

Beim Sortieren mit normalem Heapsort finden beim Absenken eines Elements zwei Vergleiche pro Ebene statt:

<ol><li>Welcher der beiden Nachfolgeknoten des abzusenkenden Elements ist größer?</li>

<li>Ist der nun bestimmte Nachfolgeknoten größer als das abzusenkende Element?</li></ol>

Nachdem ein <a href="Bin%C3%A4rbaum" title="Binärbaum">Binärbaum</a> zur Hälfte aus <a href="Blatt_(Graphentheorie)" class="mw-redirect" title="Blatt (Graphentheorie)">Blättern</a> besteht und zudem beim Sortieren ehemalige Blätter mit ohnehin schon eher niedrigen Werten abgesenkt werden, ist es wahrscheinlich, dass ein Element bis zur Blattebene oder in deren Nähe abgesenkt werden muss. Deshalb kann es lohnend sein, auf den zweiten Vergleich zu verzichten und auf Verdacht bis zur Blattebene abzusenken.

In einem zweiten Schritt wird dann rückwärts überprüft, wie weit das Element wieder angehoben werden muss. Im günstigsten Fall (sehr große Felder mit nur wenigen <a href="Dublette_(Datenbank)" title="Dublette (Datenbank)">Dubletten</a>) kann dabei fast die Hälfte der insgesamt nötigen Vergleiche bei mäßigem Zusatzaufwand eingespart werden.

Weniger geeignet ist BottomUp-Heapsort zur Sortierung kleinerer Felder mit einfacher numerischer Vergleichsoperation und dann, wenn im Feld sehr viele Elemente gleichwertig sind (dann stimmt die Annahme nicht, dass meist bis in die Nähe der Blattebene abgesenkt werden muss).

<div class="mw-heading mw-heading2"><h2 id="Algorithmus">Algorithmus</h2></div>

Konkret wird der Heapsort-Algorithmus, was das Absenken betrifft, wie folgt verändert:

Zunächst wird der Pfad, in welchem das Wurzelelement versenkt werden soll, bestimmt. Dies geschieht durch die Ermittlung des jeweils größten Kindes (Pfad maximaler Kinder). Danach wird dieser bestimmte Pfad von unten nach oben (vom Blatt in Richtung Wurzel) durchlaufen. Hierbei wird bei jedem besuchten Knoten verglichen, ob er größer als das abzusenkende Wurzelelement ist. Ist dem so, wird das Wurzelelement an die Position des zuletzt besuchten Knotens kopiert und vorher der restliche Pfad um eine Ebene nach oben verschoben.

Alternativ kann man auch die Verschiebung von vornherein auf Verdacht bis zur Blattebene durchführen und später – soweit notwendig – wieder rückgängig machen. Wo Kopien relativ günstig durchgeführt werden können (weil etwa nur ein <a href="Zeiger_(Informatik)" title="Zeiger (Informatik)">Zeiger</a> kopiert wird), kann das insgesamt vorteilhaft sein.

<div class="mw-heading mw-heading2"><h2 id="Beispiel">Beispiel</h2></div>

Heap: [9, 23, 24, 20, 18, 14, 17, 13, 15, 11, 10, 5, 7, 3, 2]

Baumstruktur:

Das Element 9 muss abgesenkt werden, da es kleiner als mindestens ein Nachfolgeknoten ist.

Es wird als erstes der Pfad der maximalen Kinder (ausgehend von der Wurzel) bestimmt. Es ergibt sich also 9 - 24 - 17 - 3.

Der Algorithmus durchläuft diesen Pfad nun von unten nach oben, also 3 → 17 → 24 → 9. Nun wird der Pfad vom Blattknoten (3) beginnend solange durchlaufen, bis sich ein Knoten findet, der größer als 9 ist. Der Durchlauf endet folglich bei 17. Nun werden alle Knoten ab 17 bis zum Nachfolgeknoten der Wurzel (= 17 → 24) um eine Ebene nach oben und der Knoten 9 an die Position von 17 verschoben. Folglich ändern 17 und 24 als Nachfolgeknoten und 9 als Wurzelknoten ihren Platz.

Heap: [24, 23, 17, 20, 18, 14, 9, 13, 15, 11, 10, 5, 7, 3, 2]

Baumstruktur:

/* start https://de.wikipedia.org/ */

.mw-parser-output .vl-mehrere-bilder{margin-top:.5em}.mw-parser-output .vl-mehrere-bilder-kopf{clear:both;font-weight:bold}.mw-parser-output .vl-mehrere-bilder-horizontal{float:left;padding:1px}@media screen{html.skin-theme-clientpref-night .mw-parser-output .vl-mehrere-bilder .thumbimage{background:none}html.skin-theme-clientpref-night .mw-parser-output .vl-mehrere-bilder .thumbimage:not([style*="background"]) span:not([class]) img{background-color:var(--background-color-base-fixed,#ffffff);color:var(--color-base-fixed,#202122);filter:brightness(0.8)}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .vl-mehrere-bilder .thumbimage{background:none}html.skin-theme-clientpref-os .mw-parser-output .vl-mehrere-bilder .thumbimage:not([style*="background"]) span:not([class]) img{background-color:var(--background-color-base-fixed,#ffffff);color:var(--color-base-fixed,#202122);filter:brightness(0.8)}}

/* end https://de.wikipedia.org/ */

</style><div class="thumb tleft vl-mehrere-bilder" style="width:522px;"><div class="thumbinner"><div class="vl-mehrere-bilder-horizontal" style="width:254px;"><div class="thumbimage"></div></div><div class="vl-mehrere-bilder-horizontal" style="width:254px;"><div class="thumbimage"></div></div><div style="clear:both;"></div>

</div></div>

<div class="mw-heading mw-heading2"><h2 id="Implementierung">Implementierung</h2></div>

Einfache Beispielsimplementierung in <a href="Varianten_der_Programmiersprache_C#C99" title="Varianten der Programmiersprache C">C99</a>:

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre> int heapsort_bu( int data[], int n ) // zu sortierendes Feld und seine Länge

{

int val, parent, child;

int root= n >> 1; // erstes Blatt im Baum

int count= 0; // Zähler für Anzahl der Vergleiche

for ( ; ; )

{

if ( root ) { // Teil 1: Konstruktion des Heaps

parent= --root;

val= data[root]; // zu versickernder Wert

}

else

if ( --n ) { // Teil 2: eigentliche Sortierung

val= data[n]; // zu versickernder Wert vom Heap-Ende

data[n]= data[0]; // Spitze des Heaps hinter den Heap in

parent= 0; // den sortierten Bereich verschieben

}

else // Heap ist leer; Sortierung beendet

break;

while ( (child= (parent + 1) << 1) < n ) // zweites (!) Kind;

{ // Abbruch am Ende des Heaps

if ( ++count, data[child-1] > data[child] ) // größeres Kind wählen

--child;

data[parent]= data[child]; // größeres Kind nach oben rücken

parent= child; // in der Ebene darunter weitersuchen

}

if ( child == n ) // ein einzelnes Kind am Heap-Ende

{ // ist übersprungen worden

if ( ++count, data[--child] >= val ) { // größer als der zu versick-

data[child]= val; // versickerten Wert eintragen

continue;

}

child= parent; // 1 Ebene nach oben zurück

}

else

{

if ( ++count, data[parent] >= val ) { // das Blatt ist größer als der

data[parent]= val; // zu versickernde Wert, der damit

continue; // direkt eingetragen werden kann

}

child= (parent - 1) >> 1; // 2 Ebenen nach oben zurück

}

while ( child != root ) // maximal zum Ausgangspunkt zurück

{

parent= (child - 1) >> 1; // den Vergleichswert haben wir bereits

// nach oben verschoben

if ( ++count, data[parent] >= val ) // größer als der zu versickernde

break; // Wert, also Position gefunden

data[child]= data[parent]; // Rückverschiebung nötig

}

return count;

}

</pre></div>

Zu Vergleichszwecken gibt die Funktion die Anzahl der durchgeführten Vergleiche zurück.

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li>J. W. J. Williams: Algorithm 232 – Heapsort. In: Communications of the ACM, 1964, 7(6), S. 347–348.</li>

<li>Robert W. Floyd: Algorithm 245 – Treesort 3. In: Communications of the ACM, 1964, 7(12), S. 701.</li>

<li>S. Carlsson: HEAPS. Doctoral dissertation, Lund Univ., Sweden 1986.</li>

<li>Svante Carlsson: Average-case results on heapsort. In: BIT, 27, 1987, no.1, S. 2–17.</li>

<li>Ingo Wegener: BOTTOM-UP-HEAPSORT, a new variant of HEAPSORT beating, on an average, QUICKSORT (if n is not very small). 15th International Symposium on Mathematical Foundations of Computer Science (MFCS ’90) Banská Bystrica, 1990. In: Theoret. Comput. Sci., 118, 1993, no. 1, S. 81–98.</li></ul></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-04-16" href="https://de.wikipedia.org/wiki/?title=Bottom-Up-Heapsort&oldid=255206335">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>